`
https://leetcode.cn/problems/network-delay-time/
`

/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {
  // 编号从 1 开始
  const graph = Array.from({ length: n + 1 }, () => [])
  for (const [from, to, weight] of times) {
    graph[from].push([to, weight])
  }
  // 记录从起点 k 到各个节点的最短路径，-1 表示还未访问
  const distTo = new Array(n + 1).fill(-1)
  // datastructures-js Heap
  const pq = new Heap((a, b) => a.distFromStart - b.distFromStart)
  pq.push(new State(k, 0))

  while (!pq.isEmpty()) {
    const { node: curNode, distFromStart: curDistFromStart } = pq.pop()
    // 已经遍历过了
    if (distTo[curNode] !== -1) continue
    distTo[curNode] = curDistFromStart

    for (const [nextNode, weight] of graph[curNode]) {
      if (distTo[nextNode] !== -1) continue
      pq.push(new State(nextNode, curDistFromStart + weight))
    }
  }

  // 找到最长的那条最短路径
  let res = 0;
  for (let i = 1; i <= n; i++) {
    if (distTo[i] === -1) {
      // 有节点不可达
      return -1;
    }
    res = Math.max(res, distTo[i]);
  }
  return res;
};

// 记录队列中的状态
class State {
  constructor(node, distFromStart) {
    // 当前节点 ID
    this.node = node;
    // 从起点 s 到当前 node 节点的最小路径权重和
    this.distFromStart = distFromStart;
  }
}